二叉树后序遍历

Posted on | In | | reads times

题目描述：
代码实现二叉树的后续遍历。要求：1、不可以用递归；2、不可以用栈；3、自定义树节点的结构；4、给出测试用例；5、语言不限；
注意：你的方法的输入为根节点

输入描述：
第一行一个正整数n(1<=n<=100)，表示二叉树有n个结点。
接下来n行，第i行两个整数li,ri (0<=li,ri<=n) ，分别表示第i个结点的左儿子和右儿子，为0代表空。
保证根为1，保证输入为合法二叉树。

输出描述：
输出一行。输出n个数，代表后序遍历的结点的顺序，相邻两个数之间用一个空格相隔。

大致思路如下，关于输入输出处理，在我另一篇关于二叉树的博客里有写：
非递归实现二叉树遍历

因为不能用栈，所以对节点做调整，加入父节点属性。
现在有父节点，我们再来看后序遍历的顺序。首先父节点，然后向左寻找，找到左节点，然后回到该节点的上一个节点，再找其右节点，再回到该节点的上一个节点。
那么起码要知道，上一节点是谁。并且实时调整上一节点。
所以假设，我们设置一个当前节点指针pCur，一个上一节点指针pLast。
每一次结束，当前指针一定是指向父节点，上一节点指针一定是指向当前指针的上一个位置。
所以存在两者情况，要么，上一节点指针指向当前指针的左节点，要么指向右节点。
所以简化成最简单的情况，

  1. pLast == pCur.left
  2. pLast == pCur.right

第一种情况，由于当前while循环寻找到的一定是叶节点，则左节点一定为空，如果同时右节点存在，那么说明存在左子树，需要遍历右子树，并判断右子树是否存在左节点，这时就是重复寻找。如果不存在右子树，则直接输出当前指针指向的节点，然后回退父节点，输出父节点，回退父节点后，不需要再遍历左节点，因为左节点此时为空，所以下一轮寻找会直接判断右节点为空，即不存在右子树，输出当前节点并回退父节点。

第二种情况，说明当前遍历到右节点，则一定是右子树遍历完毕遍历到右叶子节点，所以输出，并回退父节点。

讲的有点混乱，我还是要再琢磨一下怎么更好的阐述。。。

总之就是对于一个节点，其是否有左子树，如果有左子树，则继续沿左子树方向找到左叶子节点；如果没有左子树，看是否有右子树，有右子树，则继续将右子树当作一个二叉树进行遍历；
如果有左叶子节点就输出左叶子节点，然后看有没有右子树，如果有则继续将右子数当作二叉树遍历；
如果只有右叶子节点，则输出右叶子节点；
然后回退，输出父节点。
如何判断叶子节点，则需要每次寻找子树后，如果存在子树，则需要继续沿左一直找到左叶子节点，或一直找右叶子节点。如果没有右子树或左子树，则可以输出。
所以本解法在没有左节点，只有右叶子节点时continue，没有继续内部while循环找叶子节点。只有在判断有子树的情况下，没有continue；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
var node = function (val) {
    this.parent = null;
    this.left = null;
    this.right = null;
    this.val = val;
}
var arr = [[3, 2], [0, 5], [0, 4], [0, 0], [0, 0]];
var initTree2 = function (arr) {
    var pRoot = new node(1);
    var queue = [];
    queue.push(pRoot);
    while (queue.length != 0) {
        var pCur = queue.shift();
        console.log(pCur.val)
        var i = pCur.val - 1;
        pCur.left =new node(arr[i][0]);
        pCur.left.parent=pCur;
        pCur.right = new node(arr[i][1]);
        pCur.right.parent=pCur;
        if (pCur.left.val != 0) {
           
            queue.push(pCur.left)
        }
        if (pCur.right.val != 0) {
            
            queue.push(pCur.right);
        }
    }
    return pRoot;
}
var pRoot2=initTree2(arr);
console.log(pRoot2)
var postOrder = function (pRoot) {
    var pCur=pRoot;
    var pLast=null;
    while(pCur){
    //    console.log(1)
       if(pCur.left==pLast){
            if(pCur.right.val!=0){
                pCur=pCur.right;
            }else{
                pLast=pCur;
                console.log(pCur.val);
                pCur=pCur.parent;
                continue;
            }
       }else if(pCur.right==pLast){
            console.log(pCur.val)
            pLast=pCur;
            pCur=pCur.parent;
            continue;
       }

       while(pCur.left!=null){
           pCur=pCur.left
       }
       pLast=pCur;
       pCur=pCur.parent;
    }
}
postOrder(pRoot2);